package com.zcy.day1.homeWork.linkedList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * 手撸一个双向链表（追加末尾，中间添加，遍历，移除中间元素）可以参考源码
 * @param <T>
 */
public class LinkedListDemo<T> {
    private int size = 0;
    //头指针
    private Node<T> first;
    //尾指针
    private Node<T> last;

    static class Node<T> {
        private T data;
        private Node<T> next;
        private Node<T> prev;

        public Node(T data, Node<T> next, Node<T> prev) {
            this.data = data;
            this.next = next;
            this.prev = prev;
        }
    }


    /**
     * 将数据加入到尾部
     *
     * @param t
     */
    public void addLast(T t) {
        Node<T> node = last;
        Node<T> newNode = new Node<>(t, null, node);
        last = newNode;
        if (node == null) {
            first = newNode;
        } else {
            node.next = newNode;
        }
        size++;
    }

    /**
     * 遍历链表
     */
    public void ergodic(){
        Node<T> node = first;
        List<T> linkList = new ArrayList<>();
        while (node != null){
            linkList.add(node.data);
            node = node.next;
        }
        System.out.println(linkList);
    }

    /**
     * insert不同于set,insert在指定位置插入节点，原来的节点后移
     * @param index
     * @param t
     */
    public void insert(int index,T t) {
        rangeCheck(index);
        int curIndex=0;
        Node<T> curNode = this.first;
        while (curIndex != index) {
            curNode=curNode.next;
            curIndex++;
        }
        Node<T> prev = curNode.prev;
        Node<T> newNode = new Node<>(t, curNode, prev);
        prev.next=newNode;
        curNode.prev=newNode;
        size++;
    }


    /**
     * 删除指定位置的数据
     * @param i 索引
     * @return
     */
    public T removeAt(int i) {
        rangeCheck(i);
        int curIndex=0;
        Node<T> tNode = this.first;
        while (tNode != null && curIndex!=i) {
            tNode = tNode.next;
            curIndex++;
        }
        //走到这里可能是找到了，也可能到头了

        if (tNode == null) {
            return null;
        }
        //如果tNode！=null,说明找到指定节点了
        Node<T> prev = tNode.prev;
        Node<T> next = tNode.next;
        prev.next = next;
        next.prev = prev;
        size--;
        return tNode.data;

    }

    /**
     * 校验新增和删除元素的索引范围
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("下标越界");
        }
    }

}
